#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-01-14 18:04:05


class Node(object):
    """单链表节点"""

    def __init__(self, data, next=None):
        self.data = data  # 数据域
        self.next = next  # 链接域，指向下一个节点


class SingleLink(object):
    """单链表"""

    def __init__(self):
        self.head = None  # 头指针

    @property
    def length(self):
        """链表长度"""
        probe = self.head
        count = 0
        while probe is not None:
            count += 1
            probe = probe.next
        return count

    def is_empty(self):
        """判断链表是否为空"""
        return self.head is None

    def add(self, data):
        """往头部添加数据"""
        node = Node(data)
        node.next = self.head
        self.head = node

    def append(self, data):
        """往尾部添加数据"""
        node = Node(data)
        if self.is_empty():
            self.head = node
        else:
            probe = self.head
            while probe.next is not None:
                probe = probe.next
            probe.next = node

    def insert(self, index, data):
        """往任意位置插入数据"""
        probe = self.head
        if probe is None or index <= 0:
            self.head = Node(data)
        else:
            # 找到 index - 1 的位置
            while index > 1 and probe.next is not None:
                probe = probe.next
                index -= 1
            probe.next = Node(data, probe.next)

    def remove(self, data):
        if self.is_empty():
            return

        probe = self.head
        if probe.data == data:
            self.head = probe.next
            return

        while probe is not None:
            if probe.next.data == data:
                probe.next = probe.next.next
                return
            probe = probe.next

        raise ValueError("{} not in {}".format(data, self))

    def remove_by_index(self, index):
        assert index >= 0

        if self.is_empty():
            return

        probe = self.head
        if index == 0 or probe.next is None:  # 只有一个节点的情况
            data = probe.data
            self.head = None
        else:
            while index > 1 and probe.next.next is not None:
                probe = probe.next
                index -= 1
            # 当 probe.next.next 等于 None 时， index 可能大于 self.length - 1
            # 此时默认删除最后一个节点
            data = probe.next.data
            probe.next = probe.next.next
        return data

    def replace(self, old, new, count=-1):
        probe = self.head
        while probe is not None and count != 0:
            if probe.data == old:
                probe.data = new
                if count > 0:  # 当 count 小于 0 时，则替换所有可能的节点
                    count -= 1
            probe = probe.next

    def travel(self):
        probe = self.head
        while probe is not None:
            print(probe.data)
            probe = probe.next

    def search(self, data):
        probe = self.head
        while probe is not None:
            if probe.data == data:
                return probe.data
            probe = probe.next

    def visit(self, index):
        if self.is_empty():
            raise "{} is empty".format(self)
        if index < 0:
            raise IndexError("index out of range")

        probe = self.head
        while index > 0:
            if probe is None:
                raise IndexError("index out of range")
            probe = probe.next
            index -= 1
        return probe.data

    def check_loop(self):
        """判断链表是否有环

        使用快慢两个指针，当两个指针相遇时，则说明有环
        """
        slow = fast = self.head
        while fast and fast.next:
            slow = slow.next       # 慢指针一次走一步
            fast = fast.next.next  # 快指针一次走两步
            if slow == fast:
                return True
        return False

    def find_begin_of_loop(self):
        """当链表有环时查找环的入口"""
        slow = fast = self.head
        exist_loop = False
        while fast and fast.next:
            slow = slow.next       # 慢指针一次走一步
            fast = fast.next.next  # 快指针一次走两步
            if slow == fast:
                exist_loop = True

        if exist_loop is True:
            slow = self.head
            while slow != fast:
                fast = fast.next
                slow = slow.next
            return slow

        return False  # 不存在环


class SingleCircularLink(object):
    """单项循环链表"""


if __name__ == "__main__":
    sl = SingleLink()
    for i in range(2, 6):
        sl.append(i)
    sl.add(1)
    sl.add(0)
    sl.travel()

    print("")
    sl.insert(3, 10)
    sl.travel()

    sl.remove(10)

    print("remove index 5: ", sl.remove_by_index(5))

    sl.replace(2, 20)
    print("search 20: ", sl.search(20))

    print("")
    sl.travel()
